package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;

import util.PrintArray;

public class LongestSequence {

    public static void main(String[] args) {
        LongestSequence object = new LongestSequence();
//        int[] nums = {2, 1, 3, 2, 1, 4};
//        int[] nums2 =  {3, 2, 1, 4, 5};
//        System.out.println(object.findLength(nums, nums2));

//        String text1 = "abcba", text2 = "abcbcba";
//        System.out.println(object.longestCommonSubsequenceOptimize(text1, text2));

//        String word1 = "intention", word2 = "intentions";
//        System.out.println(object.minDistance(word1, word2));
        object.test();
    }


    public int findLength(int[] nums1, int[] nums2) {
        // dp[i][j] 表示s1[i]与s2[j] 最长公共子串
        int size1 = nums1.length;
        int size2 = nums2.length;
        int[][] dp = new int[size1][size2];
        // 执行初始化操作
        for (int j = 0; j < size2; j++) {
            if (nums2[j] == nums1[0]) {
                dp[0][j] = 1;
            }
        }
        for (int i = 0; i < size1; i++) {
            if (nums1[i] == nums2[0]) {
                dp[i][0] = 1;
            }
        }
        int res = 0;
        for (int i = 1; i < size1; i++) {
            for (int j = 1; j < size2; j++) {
                if (nums2[j] == nums1[i]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                res = Math.max(res, dp[i][j]);
            }
        }
        return res;
    }

    public int longestCommonSubstring(String text1, String text2) {
        // dp[i][j] 表示s1[i]与s2[j] 最长公共子串
        int size1 = text1.length();
        int size2 = text2.length();
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        int[][] dp = new int[size1][size2];
        // 执行初始化操作
        for (int j = 0; j < size2; j++) {
            if (s2[j] == s1[0]) {
                dp[0][j] = 1;
            }
        }
        for (int i = 0; i < size1; i++) {
            if (s1[i] == s2[0]) {
                dp[i][0] = 1;
            }
        }
        int res = 0;
        for (int i = 1; i < size1; i++) {
            for (int j = 1; j < size2; j++) {
                if (s2[j] == s1[i]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                res = Math.max(res, dp[i][j]);
            }
        }
        return res;
    }

    public int longestCommonSubsequence(String text1, String text2) {
        // dp[i][j] 表示s1[i]与s2[j] 最长公共子序列
        int size1 = text1.length() + 1;
        int size2 = text2.length() + 1;
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        int[][] dp = new int[size1][size2];
        int res = 0;
//        for (int j = 0; j < size2; j++) {
//            if (s2[j] == s1[0]) {
//                dp[0][j] = 1;
//            } else {
//                dp[0][j] = j > 0 ? dp[0][j - 1] : 0;
//            }
//            res = Math.max(res, dp[0][j]);
//
//        }
//        for (int i = 0; i < size1; i++) {
//            if (s1[i] == s2[0]) {
//                dp[i][0] = 1;
//            } else {
//                dp[i][0] = i > 0 ? dp[i - 1][0] : 0;
//            }
//            res = Math.max(res, dp[i][0]);
//        }
        for (int i = 1; i < size1; i++) {
            for (int j = 1; j < size2; j++) {
                if (s2[j - 1] == s1[i - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
                res = Math.max(res, dp[i][j]);
            }
        }
        return res;
    }

    // 这个稍微有点问题，"abcba", text2 = "abcbcba" 会返回6
    // 可以看注释修改的地方
    public int longestCommonSubsequenceOptimize(String text1, String text2) {
        // dp[i][j] 表示s1[i]与s2[j] 最长公共子序列
        int size1 = text1.length() + 1;
        int size2 = text2.length() + 1;
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        int[] dp = new int[size2];
        int res = 0;
        for (int i = 1; i < size1; i++) {
            int lastLeft = dp[0];
            for (int j = 1; j < size2; j++) {
                // 把dp[j]存起来，j + 1的左上角就是这个值
                int tmp = dp[j];
                if (s2[j - 1] == s1[i - 1]) {
                    // 这个dp[j - 1] 已经是dp[i][j - 1]了，而不是dp[i - 1][j - 1]
                    // dp[j] = dp[j - 1] + 1;
                    dp[j] = lastLeft + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                res = Math.max(res, dp[j]);
                lastLeft = tmp;
            }
            PrintArray.printArray(dp);
        }
        return res;
    }

    // 你可以对一个单词进行如下三种操作：
    //
    // 插入一个字符
    // 删除一个字符
    // 替换一个字符
    // 求最小编辑距离
    public int minDistance(String word1, String word2) {
        if (word1 == null || word1.length() <= 0 || word2 == null || word2.length() <= 0) {
            return (word1 == null || word1.length() <= 0) ? word2.length() : word1.length();
        }
        // dp[i][j] 表示s1和s2所需要的编辑距离
        // 在k个操作中，将a[1...i]转换为b[1...j-1]
        // 在k个操作中，将a[1...i-1]转换为b[1...j]
        // 在k个操作中，将a[1...i-1]转换为b[1...j-1]
        // 针对第一种情况，只需要在a[1...i]后加上字符b[j]，即可完成a[1..i]到b[1...j]的转换，总共需要的编辑次数即为k+1。
        // 针对第二种情况，只需要在a[i]字符从a中移除，即可完成a[1..i]到b[1...j]的转换，总共需要的编辑次数即为k+1。
        // 针对第三种情况，只需要将a[i]转换为b[j]，即可完成a[1..i]到b[1...j]的转换，如果a[i]与b[i]的字符相同，则总共需要的编辑次数为k，否则即为k+1。
        // 所以上述三种情况分别对应于插入、删除、替换操作。

        int size1 = word1.length() + 1;
        int size2 = word2.length() + 1;
        char[] s1 = word1.toCharArray();
        char[] s2 = word2.toCharArray();
        int[][] dp = new int[size1][size2];
        // 执行初始化操作
        for (int j = 1; j < size2; j++) {
            dp[0][j] = j;
        }
        // 执行初始化操作
        for (int i = 1; i < size1; i++) {
            dp[i][0] = i;
        }

        for (int i = 1; i < size1; i++) {
            for (int j = 1; j < size2; j++) {
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j - 1])) + 1;
                }
            }
        }
        return dp[size1 - 1][size2 - 1];
    }

    public void test() {
        ArrayList<String> list = new ArrayList<>();
        list.add("1");
        list.add("2");
        list.add("3");
//        for (int i = 0; i < list.size(); i++) {
//            if (list.get(i).equals("1")) {
//                list.remove(i);
//            }
//        }
//        for (String s : list) {
//            if (s.equals("1")) {
//                list.remove(s);
//            }
//        }
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String s = iterator.next();
            if (s.equals("1")) {
                iterator.remove();
            } else {
                System.out.println(s);
            }
        }
    }
}
